package Work3;

import java.util.Random;

public class Doublequicksort {
	public static void main(String[] args) {
		int arr[]=Createarr();
		System.out.println("随机生成长度在6-10间,取值在1-15间的数组");
		System.out.printf("排序前:");
		PrintArr(arr);
		quick(arr,0,(arr.length-1));
		System.out.printf("排序后:");
		PrintArr(arr);
	}
	
	public static int[] Createarr() {
		Random rd = new Random();
		int n = rd.nextInt(6,11);
		int[] arr=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=rd.nextInt(1,16);
		}
		return arr;
	}
	
	public static int sort(int[] arr,int left,int right) {
		int pv=arr[left];
		int first=left;
		int temp;
		while(true) {
			while(arr[right]>pv&&left<right) {
				right--;
			}
			while(arr[left]<=pv&&left<right) {
				left++;
			}
			if(left<right) {
				temp=arr[left];
				arr[left]=arr[right];
				arr[right]=temp;
			}else {
				temp=arr[first];
				arr[first]=arr[right];
				arr[right]=temp;
				return right;
			}
		}
	}
	
	public static void quick(int[] arr,int first,int last) {
		if(first>=last) {
			return;
		}
		int p=sort(arr,first,last);
		quick(arr,first,p-1);
		quick(arr,p+1,last);
	}
	
	public static void PrintArr(int[] arr) {
		System.out.printf("[");
		for(int i=0;i<arr.length;i++) {
			if(i!=arr.length-1) {
				System.out.printf(arr[i]+",");
			}else {
				System.out.printf("%d",arr[i]);
			}
		}
		System.out.printf("]\n");
	}
	
}
